//给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
//
// 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
//
//
//
// 示例 1：
//
//
//输入: s1 = "ab" s2 = "eidbaooo"
//输出: True
//解释: s2 包含 s1 的排列之一 ("ba").
//
//
// 示例 2：
//
//
//输入: s1= "ab" s2 = "eidboaoo"
//输出: False
//
//
//
//
// 提示：
//
//
// 1 <= s1.length, s2.length <= 10⁴
// s1 和 s2 仅包含小写字母
//
//
//
//
// 注意：本题与主站 567 题相同： https://leetcode-cn.com/problems/permutation-in-string/
// Related Topics 哈希表 双指针 字符串 滑动窗口 👍 29 👎 0

package leetcode.editor.cn;

@SuppressWarnings("all")
//Java：字符串中的变位词
public class 字符串中的变位词 {
    public static void main(String[] args) {
        Solution solution = new 字符串中的变位词().new Solution();
        // TO TEST
        String s1 = "ab";
        String s2 = "eidbaooo";
        System.out.println(solution.checkInclusion(s1, s2));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean checkInclusion(String s1, String s2) {
            if (s1.length() > s2.length())
                return false;

            int[] count = new int[26];

            for (int i = 0; i < s1.length(); i++) {
                int index = s1.charAt(i) - 'a';
                count[index]++;
            }


            int left = 0, right = 0;
            while (left <= right && right < s2.length()) {

                int ch = s2.charAt(right) - 'a';
                count[ch]--;

                if (right >= s1.length() - 1) {

                    if (check(count))
                        return true;

                    count[s2.charAt(left) - 'a']++;
                    left++;
                }

                right++;
            }


            return false;
        }

        private boolean check(int[] count) {

            for (int i = 0; i < count.length; i++) {

                if (count[i] > 0)
                    return false;

            }

            return true;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)


}
